Konsztantinosz Gavrasz néven született Athénban, a politika iránti érdeklődést görög-orosz szülei oltották belé. Köztisztviselő apja a náci megszállás alatt a görög ellenállás baloldalához tartozó szervezetben harcolt, ezért a háború után megkapta a kommunista címkét. Apja múltja miatt Costa-Gavras görög egyetemre nem iratkozhatott be, és az Egyesült Államokba sem engedték be, ahol filmkészítést akart tanulni. A középiskola elvégzése után így Franciaországba költözött, ahol 1951-ben a jogi egyetemre jelentkezett. Az állampolgárságot 1956-ban kapta meg.
Még abban az évben a filmfőiskolára iratkozott át, ennek elvégzése után rendezőasszisztens volt többek között René Clair és Henri Verneuil mellett. Első önálló filmje 1965-ben a Tökéletes bűntény című krimi volt, első nagy nemzetközi sikerét a Z, avagy egy politikai gyilkosság anatómiája című filmjével aratta 1969-ben. A görögországi katonai diktatúra hatalomra jutása után játszódó alkotás, amely a baloldali politikus Grigorisz Lambrakisz meggyilkolását dolgozza fel, megkapta a legjobb külföldi filmnek és a legjobb vágásnak járó Oscar-díjat, Cannes-ban pedig elnyerte a zsűri díját.
Az 1970-ben bemutatott A vallomás témájául a prágai Slansky-per, a csehszlovák kommunista párt főtitkára ellen 1952-ben lezajlott koncepciós per szolgált. A latin-amerikai forradalmi szervezkedések ihlették Ostromállapot című filmjét, Yves Montand főszereplésével. A zsidók második világháborús deportálása, a nácikkal való együttműködés volt a témája a Különleges ügyosztálynak és a Berlinben Arany Medvével díjazott Zenedoboz című filmjének.
A chilei diktatúra korszakát elevenítette meg első amerikai filmje, az Eltűntnek nyilvánítva (Missing), amely elnyerte a legjobb adaptált forgatókönyvért járó Oscar-díjat Cannes-ban is díjazták. A rendkívül jól felépített, feszült drámában az eltűnt amerikai újságíró után hiába nyomozó Jack Lemmon nyújtott emlékezetes alakítást. A rendező nem politikai témájú filmjei közül kiemelkedik a Romain Gary regénye alapján készült Női fény és a Családi balhé című krimiparódia.
A palesztin kérdést boncolgató Hanna K. (1983) miatt sok támogatóját elvesztette, ugyanakkor új híveket is szerzett. Az 1988-as Elárulva amerikai rasszista gyilkosságokat leplezett le, A kis apokalipszisben hajdani balos párizsi értelmiségiekről adott szatirikus képet. Az Őrült város vegyes fogadtatásban részesült, de Dustin Hoffman és John Travolta játéka, a feszültséggel teli cselekmény és a rendezői rutin azért ezt a filmet is sikeressé tette.
2002-ben sokakat sokkolt Ámen című filmje, amely Rolf Hochhuth A helytartó című, korábban már nagy viharokat kavart drámája alapján készült: ebben a szerző azt állította, hogy XII. Piusz pápa tudott a holokausztról, de nem emelte fel hangját a zsidók megmentése érdekében; a vitákat fokozta a Benetton-kampányokból megismert Oliviero Toscani által komponált filmplakát is. A film 2003-ban elnyerte a legrangosabb francia filmes kitüntetést, a César-díjat. 2006-ban készült el Az ezredes című háborús drámája, majd 2009-ben Az Éden Nyugatra van című filmje az illegális bevándorlás útvesztőiről.
Costa-Gavras 2008-ban a Berlinale zsűrijének elnöke volt. Láthattuk a 2010-es, 63. cannes-i filmfesztiválról szóló magyar televíziós dokumentumfilmben és a Jean-Louis Trintignant-ról szóló 2012-ben készült dokumentumfilm egyik szereplőjeként.
Tavaly a XX. Századi Humanista Filmrendező-díjjal tüntette ki az International League of Humanists (ILH) nevű szervezet a balkáni háborúk idején tett béketeremtő törekvéseiért.